package optimizer;

import java.util.ArrayList;

public class DependencyTable {
	private int totalTime;
	ArrayList<DependencyTableRow> container;

	private DependencyTable successer;
	private DependencyTable target;

	private DependencyTable() {
		this.container = new ArrayList<DependencyTableRow>();
	}

	public static DependencyTable buildDependencyTable(BasicBlock instructionSet){
		DependencyTable table = new  DependencyTable();

		int currentClockCycle = 1;
		Tracker tracker = new Tracker(currentClockCycle);

		System.out.println("Log - DependencyTable.buildDependencyTable() : ");
		System.out.println("______________________________________________________________");
		System.out.println("|Cycle#\t|Line#\t|W Reg\t|R Regs\t\t|Op\t|Dependencies");
		System.out.println("|-------|-------|-------|---------------|-------|-------------");
		for(int i=0; i<instructionSet.getBlockSize(); i++) {
			Instruction ins = instructionSet.getInstrcutionAtIndex(i);
			DependencyTableRow row = null;
			do {
				row = new DependencyTableRow(i+1, ins, tracker, false);
				row.printDependencyRow();
				table.container.add(row);
			} while(row.getInstruction().op == "STALL");
		}
		System.out.println("|=======|=======|=======|===============|=======|=============");
		table.totalTime = tracker.getClockcycle()-1;
		return table;
	}

	public DependencyTable optimize() {
		System.out.println("\nLog - DependencyTable.optimize() : ");
		return this.optimizeDelayedBranches();
	}

	private DependencyTable optimizeDelayedBranches() {
		System.out.println("Log - DependencyTable.optimizeDelayedBranches() : ");
		DependencyTable optimizedTable = null;

		int branchindex = locateDelayedBranchSlot();
		if(branchindex >= 0) {
			//optimizedTable = fillDelayedBranchSlotFromBefore(branchindex, new ArrayList<Integer>());

			//if(optimizedTable == null) {
			//	optimizedTable = fillDelayedBranchSlotFromTarget(branchindex, new ArrayList<Integer>());
			//}
			//if(optimizedTable == null) {
				optimizedTable = fillDelayedBranchSlotFromAfter(branchindex, new ArrayList<Integer>());
			//}

			if(optimizedTable == null) {
				System.out.println("Cannot optimize the branch : " + this.container.get(branchindex).getCycleNumber() + " Originaly at :" + this.container.get(branchindex).getOrininalLineNumber());
			}
		}
		else {
			System.out.println("No branch instruction, can live happily ever after :)");
		}
		return optimizedTable;
	}

	private int locateDelayedBranchSlot() {
		for (int i=0; i<this.container.size(); i++) {
			DependencyTableRow s = this.container.get(i);
			// Unlike other two here we do not adding s.  ie //	newTable.container.add(s);
			if (s!=null) {
				// branch instruction match <also appear in DependencyTableRow:DependencyTableRow()>
				if ( "BNEZ".equalsIgnoreCase(s.getInstruction().op) || "BEQZ".equalsIgnoreCase(s.getInstruction().op)) {
					return i;
				}
			}
		}
		return -1;
	}

	private Boolean isHazardous(DependencyTableRow originalBefore, DependencyTableRow originalAfter) {
		if( (	originalBefore.getWrittenTo() != null &&
				(
						originalBefore.getWrittenTo() == originalAfter.getReadFrom1() ||
						originalBefore.getWrittenTo() == originalAfter.getReadFrom2() ||
						originalBefore.getWrittenTo() == originalAfter.getWrittenTo()
						)
				) 
				||
				(	originalAfter.getWrittenTo() != null &&
				(	
						originalAfter.getWrittenTo() == originalBefore.getReadFrom1() ||
						originalAfter.getWrittenTo() == originalBefore.getReadFrom2() ||
						originalAfter.getWrittenTo() == originalBefore.getWrittenTo()
						)
						)
				) {
			return true;
		}
		return false;
	}

	private DependencyTable fillDelayedBranchSlotFromBefore(int branchindex, ArrayList<Integer> skipindexes) {
		// find for there exists a suitable instruction for delayedbranch slot
		int movinglineindex = findDelayedBranchSlotFromBefore(branchindex, skipindexes);
				
		if(movinglineindex >= 0) {
			DependencyTable newTable = new DependencyTable();
			int currentClockCycle = 1;
			Tracker tracker = new Tracker(currentClockCycle);

			System.out.println("Log - DependencyTable.fillDelayedBranchSlotFromBefore() : ");
			System.out.println("______________________________________________________________");
			System.out.println("|Cycle#\t|Line#\t|W Reg\t|R Regs\t\t|Op\t|Dependencies");
			System.out.println("|-------|-------|-------|---------------|-------|-------------");
			

			// 1. Add instructions to new table until find a branch excluding moving instruction
			int a=0;
			for (; a<=branchindex; a++) {
				
				// Avoid moving instruction adding to its previous position
				if(a==movinglineindex) continue;
				
				DependencyTableRow r = this.container.get(a);
				if(r!=null && r.getInstruction().op != "STALL") {
					
//					if("BEQZ".equalsIgnoreCase(r.getInstruction().op)
//							|| "GOTO".equalsIgnoreCase(r.getInstruction().op)
//							|| "DATA".equalsIgnoreCase(r.getInstruction().op)
//							|| "HALT".equalsIgnoreCase(r.getInstruction().op)
//							|| "IN".equalsIgnoreCase(r.getInstruction().op)
//							|| "OUT".equalsIgnoreCase(r.getInstruction().op)
//							) {
//						return null;
//					}
					
					
					DependencyTableRow newRow = null;
					do {
						newRow = new DependencyTableRow(r.getOrininalLineNumber(), r.getInstruction(), tracker, false);
						newRow.printDependencyRow();
						newTable.container.add(newRow);
					} while(newRow.getInstruction().op == "STALL");
				}
				else {
					if(r.getInstruction().op != "STALL")
						System.out.println("ERROR - DependencyTable.fillDelayedBranchSlotFromBefore() : cannot contain null values in dependency table");
				}
			}
			
			// 2. Adding selected instruction to delayedbranchslot
			DependencyTableRow movingRow = this.container.get(movinglineindex);
			DependencyTableRow movingRowCopy = new DependencyTableRow(movingRow.getOrininalLineNumber(), movingRow.getInstruction(), tracker, true);
			movingRowCopy.printDependencyRow();
			newTable.container.add(movingRowCopy);
			if(movingRowCopy.getInstruction().op == "STALL")
				System.out.println("ERROR - DependencyTable.fillDelayedBranchSlotFromBefore() : DelayedBranch instruction cannot be a STALL after the optimization");


			// 3. Continue adding instruction from that
			a++; // for skipping delayed branch slot				
			for (; a<this.container.size(); a++) {
				DependencyTableRow r = this.container.get(a);
				if(r!=null && r.getInstruction().op != "STALL") {
					DependencyTableRow newRow = null;
					do {
						newRow = new DependencyTableRow(r.getOrininalLineNumber(), r.getInstruction(), tracker, false);
						newRow.printDependencyRow();
						newTable.container.add(newRow);
					} while(newRow.getInstruction().op == "STALL");
				}
				else {
					if(r.getInstruction().op != "STALL")
						System.out.println("ERROR - DependencyTable.fillDelayedBranchSlotFromAfter() : cannot contain null values in dependency table");
				}
			}
			System.out.println("|=======|=======|=======|===============|=======|=============");
			newTable.totalTime = tracker.getClockcycle()-1;
			
			// Now new table is build completed.
			
			// Checking new table is efficient than the old one
			if(newTable.totalTime <= this.totalTime) {
				// Use new table
				return newTable;
			}
			else {
				System.out.println("Log - DependencyTable.fillDelayedBranchSlotFromBefore() : Rejecting newTable with movingindex="+movinglineindex+" since newtable takes "+newTable.totalTime+" clockcycles while original one takes only "+this.totalTime+" clockcycles");
				skipindexes.add(movinglineindex);
				return this.fillDelayedBranchSlotFromBefore(branchindex, skipindexes);
			}
		}

		return null;
	}

	private int findDelayedBranchSlotFromBefore(int branchindex, ArrayList<Integer> skip) {
		int movinglineindex = -1;
		
		// Should check for suitable instruction from branchindex to beginning.
		for(int i=branchindex-1; i>=0; i--) {
			if(skip.contains(i))
				continue;
			
			DependencyTableRow movingRow = this.container.get(i);
			boolean isDependent = false;


			if(movingRow!=null && !"STALL".equalsIgnoreCase(movingRow.getInstruction().op)) {

				if("BEQZ".equalsIgnoreCase(movingRow.getInstruction().op)
						|| "GOTO".equalsIgnoreCase(movingRow.getInstruction().op)
						|| "DATA".equalsIgnoreCase(movingRow.getInstruction().op)
						|| "HALT".equalsIgnoreCase(movingRow.getInstruction().op)
						|| "IN".equalsIgnoreCase(movingRow.getInstruction().op)
						|| "OUT".equalsIgnoreCase(movingRow.getInstruction().op)
						) {
					return -1;
				}
				
				
				int j=i+1;
				for(;j<=branchindex+1; j++) {
					// checks for RAW, WAR, WAW hazards
					isDependent = this.isHazardous(movingRow, this.container.get(j));
					if(isDependent)
						break;
				}

				// check whether movingRow can be moved down to delayedbranchSlot
				if(isDependent) {
					// if dependent, check next instruction for moving
					continue; 
				}

				// if it can be moved
				// checking for instruction placing in delayedbranch slot => (branchindex+1)
//				for (Register r : this.container.get(branchindex+1).getDependencies()) {
//					// checks for the RAW hazards may occur
//					if (r==null || r == movingRow.getReadFrom1() || r == movingRow.getReadFrom2()) {
//						isDependent = true;
//						break;
//					}
//				}

				if(isDependent) {
					// if dependent, check next instruction for moving
					continue; 
				}

				// Hence here movingRow can be moved down and placed in the Delayed Branch slot without any hazard
				movinglineindex = i;
				System.out.println("Fill before >> Line : " + movingRow.getOrininalLineNumber() + " can be moved down to delayed branch slot for the branch : " + (this.container.get(branchindex).getOrininalLineNumber()));

				return movinglineindex;
			}
		}
		return movinglineindex;
	}

	private DependencyTable fillDelayedBranchSlotFromTarget(int branchindex, ArrayList<Integer> skipindexes) {
		return null;
	}

	private int findDelayedBranchSlotFromTarget(int branchindex, ArrayList<Integer> skip) {
		int movinglineindex = -1;

//		// Should check for suitable instruction from branchindex to end.
//		for(int i=branchindex+1;i<this.container.size(); i++) {
//			if(skip.contains(i))
//				continue;
//			
//			DependencyTableRow movingRow = this.container.get(i);
//			boolean isDependent = false;
//
//
//			if(movingRow!=null && !"STALL".equalsIgnoreCase(movingRow.getInstruction().op)) {
//				int j=i-1;
//				for(;j>=branchindex+1; j--) {
//					// checks for RAW, WAR, WAW hazards
//					isDependent = this.isHazardous(this.container.get(j), movingRow);
//					if(isDependent)
//						break;					
//				}
//
//				// check whether movingRow can be moved up to delayedbranchSlot
//				if(isDependent) {
//					// if dependent, check next instruction for moving
//					continue; 
//				}
//
//				// if it can be moved
//				// checking for instruction placing in delayedbranch slot => (branchindex+1)
//				for (Register r : this.container.get(branchindex+1).getDependencies()) {
//					// checks for the RAW hazards may occur
//					if (r==null || r == movingRow.getReadFrom1() || r == movingRow.getReadFrom2()) {
//						isDependent = true;
//						break;
//					}
//				}
//
//				if(isDependent) {
//					// if dependent, check next instruction for moving
//					continue; 
//				}
//
//				// Hence here movingRow can be moved up and placed in the Delayed Branch slot without any hazard
//				movinglineindex = i;
//				System.out.println("Fill after >> Line : " + movingRow.getOrininalLineNumber() + " can be moved up to delayed branch slot for the branch : " + (this.container.get(branchindex).getOrininalLineNumber()));
//
//			}
//		}
		return movinglineindex;
	}

	private DependencyTable fillDelayedBranchSlotFromAfter(int branchindex, ArrayList<Integer> skipindexes) {
		// find for there exists a suitable instruction for delayedbranch slot
		int movinglineindex = findDelayedBranchSlotFromAfter(branchindex, skipindexes);

		if(movinglineindex >= 0) {
			DependencyTable newTable = new DependencyTable();
			int currentClockCycle = 1;
			Tracker tracker = new Tracker(currentClockCycle);

			System.out.println("Log - DependencyTable.fillDelayedBranchSlotFromAfter() : ");
			System.out.println("______________________________________________________________");
			System.out.println("|Cycle#\t|Line#\t|W Reg\t|R Regs\t\t|Op\t|Dependencies");
			System.out.println("|-------|-------|-------|---------------|-------|-------------");
			
			// 1. Just simply add instructions to new table until find a branch
			int a=0;
			for (; a<=branchindex; a++) {
				DependencyTableRow r = this.container.get(a);
				if(r!=null && r.getInstruction().op != "STALL") {
					
					DependencyTableRow newRow = null;
					do {
						newRow = new DependencyTableRow(r.getOrininalLineNumber(), r.getInstruction(), tracker, false);
						newRow.printDependencyRow();
						newTable.container.add(newRow);
					} while(newRow.getInstruction().op == "STALL");
				}
				else {
					if(r.getInstruction().op != "STALL")
						System.out.println("ERROR - DependencyTable.fillDelayedBranchSlotFromAfter() : cannot contain null values in dependency table");
				}
			}


			// 2. Adding selected instruction to delayedbranchslot
			DependencyTableRow movingRow = this.container.get(movinglineindex);
			DependencyTableRow movingRowCopy = new DependencyTableRow(movingRow.getOrininalLineNumber(), movingRow.getInstruction(), tracker, true);
			movingRowCopy.printDependencyRow();
			newTable.container.add(movingRowCopy);
			if(movingRowCopy.getInstruction().op == "STALL")
				System.out.println("ERROR - DependencyTable.fillDelayedBranchSlotFromAfter() : DelayedBranch instruction cannot be a STALL after the optimization");


			// 3. Continue adding instruction from that
			a++; // for skipping delayed branch slot				
			for (; a<this.container.size(); a++) {
				
				// Avoid moving instruction adding to its previous position
				if(a==movinglineindex) continue;
				
				DependencyTableRow r = this.container.get(a);
				if(r!=null && r.getInstruction().op != "STALL") {
					DependencyTableRow newRow = null;
					do {
						newRow = new DependencyTableRow(r.getOrininalLineNumber(), r.getInstruction(), tracker, false);
						newRow.printDependencyRow();
						newTable.container.add(newRow);
					} while(newRow.getInstruction().op == "STALL");
				}
				else {
					if(r.getInstruction().op != "STALL")
						System.out.println("ERROR - DependencyTable.fillDelayedBranchSlotFromAfter() : cannot contain null values in dependency table");
				}
			}
			System.out.println("|=======|=======|=======|===============|=======|=============");
			newTable.totalTime = tracker.getClockcycle()-1;
			
			// Now new table is build completed.
			
			// Checking new table is efficient than the old one
			if(newTable.totalTime <= this.totalTime) {
				// Use new table
				return newTable;
			}
			else {
				System.out.println("Log - DependencyTable.fillDelayedBranchSlotFromAfter() : Rejecting newTable with movingindex="+movinglineindex+" since newtable takes "+newTable.totalTime+" clockcycles while original one takes only "+this.totalTime+" clockcycles");
				skipindexes.add(movinglineindex);
				return this.fillDelayedBranchSlotFromAfter(branchindex, skipindexes);
			}
		}

		return null;
	}

	private int findDelayedBranchSlotFromAfter(int branchindex, ArrayList<Integer> skip) {
		int movinglineindex = -1;

		// Should check for suitable instruction from branchindex to end.
		for(int i=branchindex+1;i<this.container.size(); i++) {
			if(skip.contains(i))
				continue;
			
			DependencyTableRow movingRow = this.container.get(i);
			boolean isDependent = false;


			if(movingRow!=null && !"STALL".equalsIgnoreCase(movingRow.getInstruction().op)) {

				if("BEQZ".equalsIgnoreCase(movingRow.getInstruction().op)
						|| "GOTO".equalsIgnoreCase(movingRow.getInstruction().op)
						|| "DATA".equalsIgnoreCase(movingRow.getInstruction().op)
						|| "HALT".equalsIgnoreCase(movingRow.getInstruction().op)
						|| "IN".equalsIgnoreCase(movingRow.getInstruction().op)
						|| "OUT".equalsIgnoreCase(movingRow.getInstruction().op)
						) {
					return -1;
				}				
				int j=i-1;
				for(;j>=branchindex+1; j--) {
					// checks for RAW, WAR, WAW hazards
					isDependent = this.isHazardous(this.container.get(j), movingRow);
					if(isDependent)
						break;					
				}

				// check whether movingRow can be moved up to delayedbranchSlot
				if(isDependent) {
					// if dependent, check next instruction for moving
					continue; 
				}

				// if it can be moved
				// checking for instruction placing in delayedbranch slot => (branchindex+1)
				for (Register r : this.container.get(branchindex+1).getDependencies()) {
					// checks for the RAW hazards may occur
					if (r==null || r == movingRow.getReadFrom1() || r == movingRow.getReadFrom2()) {
						isDependent = true;
						break;
					}
				}

				if(isDependent) {
					// if dependent, check next instruction for moving
					continue; 
				}

				// Hence here movingRow can be moved up and placed in the Delayed Branch slot without any hazard
				movinglineindex = i;
				System.out.println("Fill after >> Line : " + movingRow.getOrininalLineNumber() + " can be moved up to delayed branch slot for the branch : " + (this.container.get(branchindex).getOrininalLineNumber()));
				return movinglineindex;
			}
		}
		return movinglineindex;
	}
	
	public String getTable() {
		String table ="";
		table = table.concat(DependencyTableRow.getHeader());

		for (int i=0; i<this.container.size(); i++) {
			DependencyTableRow s = this.container.get(i);
			if (s!=null) {
				table = table.concat(s.getLine());
			}
		}
		table = table.concat(DependencyTableRow.getFooter());
		
		return table;
	}
	
	public String getProgram() {
		String program ="";

		for (int i=0; i<this.container.size(); i++) {
			DependencyTableRow s = this.container.get(i);
			if (s!=null) {
				program = program.concat(s.getInstruction().originalInstruction+"\n");
			}
		}		
		return program;
	}
}
